package org.example.SolutionNew006;

public class BinarySearch001 {
    public static void main(String[] args) {
        BinarySearch001 binarySearch001 = new BinarySearch001();
        int[] nums={1,3,5,6};
        System.out.println(binarySearch001.searchInsert(nums,2));

    }

    public int searchInsert1(int[] nums, int target) {
        //二分查找，找到了就返回下标，没找到就返回最好找的位置的右边
        int n = nums.length;
        return findTarget(nums,target,0,n-1);
    }

    public int findTarget(int[] nums, int target, int start, int end) {
        if(start>end){
            return start;
        }
        int mid =start + (end-start)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            return findTarget(nums,target,start,mid-1);
        }else{
            return findTarget(nums,target,mid+1,end);
        }
    }

    public int searchInsert(int[] nums, int target) {
        int start=0,end=nums.length-1;
        while(start<=end){
            int mid=start+(end-start)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return start;
    }
}
